#include <iostream>
#include <vector>

using namespace std;

// 时间复杂度O(n^2) 最直观的解法
int removeElement(vector<int>& nums, int val) {
    int len = nums.size();
    for (int i = 0; i < len; i++) {
        if (nums[i] == val) {
            for (int j = i; j < len - 1; j++) {
                nums[j] = nums[j + 1];
            }
            len--;
            i--; // 下表i之后的数已经向前移动一位，i也要向前移动一位
        }
    }

    return len;
}

// 双指针
// 定义：快指针指代需要被插入到新数组中的元素下标
// 慢指针指代坑位下标（慢指针是坑，快指针是萝卜）
int removeElement1(vector<int>& nums, int val) {
    int slow = 0, fast = 0, len = nums.size();
    for (; fast < len; fast++) {
        if (nums[fast] == val) {
            // 快指针找到了需要删除的元素，坑位留着fast继续往后走
        } else {
            // 不需要删除的元素留下
            nums[slow] = nums[fast];
            // 坑位用完往后走
            // 坑位的个数就是新数组的长度
            slow++;
        }
    }

    return slow;
}

int main() {
    vector<int> nums = {0,1,2,2,3,0,4,2};
    int result = removeElement1(nums, 2);
    cout << "result: " << result << endl;
    for (int i = 0, len = nums.size(); i < len; i++) {
        cout << "nums[" << i << "] = " << nums[i] << endl;
    }
}